In executing programs on computers, pointers are often used as references by containing values that enable a program to indirectly access a particular datum such as a variable or a record in the computer's memory or in some other storage device. A reference refers to the datum, and accessing the datum is called dereferencing the reference. Pointers can have an intimate relationship to the underlying hardware in a computer. Pointers store an address of a memory location, e.g., an actual address, or more typically, a virtual address that is translated to an address by a memory management unit. Because pointers directly store an address instead of a value, inappropriate use of pointers can lead to undefined behavior in a program. For example, modern computers when executing a program include a heap, essentially the “free” memory available for storage of data that is to be used by a program, and a stack, e.g., for short-term use of data, e.g., for use by a function in a program for local variables from the time the function is called until the function returns to the entity that called it. When a portion of memory, e.g., of a heap or stack is allocated, the portion has an associated pointer that points to a location in the memory portion, e.g., by initially containing a starting address—possibly a virtual address—of the memory portion. In the case of a heap, pointer misuse is possible. One example is an out-of-bound pointer. For example, during program execution, pointer arithmetic may be carried out on a pointer, allocated for a memory portion, which leads to the pointer's pointing to a location in memory that is not within the allocated memory portion. Dereferencing the pointer, that is, accessing the memory pointed to by following the path to the memory location, e.g., the memory address pointed to by the pointer, then leads to an error. Another example is use of a dead pointer—a pointer that points to a memory that has been de-allocated. Stack problems include stack buffer overrun that can occur, for example, when a first function calls a second function. The first function has a first stack portion allocated to it and the second function has a second stack portion allocated to it. Normally, the second function may use only the second stack portion allocated to it. However, an error can occur when the second function somehow uses the first stack portion. Such a stack problem may go undetected until execution returns to the first calling function. As an example, suppose the second function sends back to the first calling function a pointer that is in the second stack's allocation. Returning to the first function causes the second stack to be de-allocated, thus causing the returned pointer to become a dead pointer. The possibility of such pointer errors has security implications. It is therefore important to protect memory by containing memory access.
One method of protecting memory by avoiding improper memory accesses by a pointer is to use part of the pointer, e.g., the first byte of a pointer, to enter, e.g., at the time of memory allocation, a tag value, sometimes called a color, which can be randomly or otherwise assigned at the time of allocation. Associated with heap memory is a provided tag array, with each tag array element sufficient to store a tag value, e.g., one byte, with one tag array element per unit of heap memory, e.g., per block. A block, e.g., may be 512 bytes of memory. At the time of memory allocation, the same tag value that is assigned to the pointer is also stored in each tag array element corresponding to the allocated memory portion. The tag value, for example, may be randomly assigned from all the unassigned values. Consider a tag that is one byte long. As an example, if a 34 KB portion of memory is allocated, a pointer is allocated, the tag field of the pointer is assigned a tag value, and, for a block size of 512 bytes, 68 locations of the tag array are tagged with the same tag value as the pointer for the allocation. Consider now an attempted access to a location in the allocated portion, i.e., an attempted dereference. A determination is made to ascertain whether the pointer that points to a location in the allocated portion has the same tag value as the tag array elements corresponding to the pointed to location, and access is prevented if these tag values are not the same. When deallocating the portion of memory, the tag value is freed up for reuse.
The approaches described in this BACKGROUND section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section. Similarly, issues identified with respect to one or more approaches should not be assumed to have been recognized in any prior art on the basis of this section, unless otherwise indicated.